

/**
 * 
 * RBTree
 * 
 * An implementation of a Red Black Tree with non-negative, distinct integer
 * values
 * 
 */

public class RBTree {

	private final RBNode nil = new RBNode(-1, null, null, null,
			TreeNodeColor.BLACK);

	private int size;
	private int toIntArrayIterator;
	private RBNode root;

	/**
	 * Constructs RBTree. Assigns default values.
	 */
	public RBTree() {
		root = nil;
		size = 0;
	}

	/**
	 * public void insert(int i)
	 * 
	 * inserts the integer i into the binary tree; the tree must remain valid
	 * (keep its invariants). the function returns the number of color flips, or
	 * 0 if i was already in the tree
	 * 
	 * O(log(n)), where n=this.size
	 */
	public int insert(int i) {
		RBNode destination = nodeSearch(i);
		if (destination.key == i) {
			return 0;
		}

		RBNode parent = destination;
		size++;
		RBNode z = new RBNode(i, nil, nil, parent, TreeNodeColor.RED);
		if (empty()) {
			root = z;
			return changeColor(z, TreeNodeColor.BLACK);
		} else if (i < parent.key) {
			parent.setLeft(z);
		} else {
			parent.setRight(z);
		}
		return insertFix(z);
	}

	/**
	 * Fixes the color/structure of the RB tree to maintain the black and red
	 * rule
	 * 
	 * */
	private int insertFix(RBNode z) {
		int colorChanges = 0;
		while (z.getParent().getColor() == TreeNodeColor.RED) {
			if (isLeftChild(z.getParent())) {
				// Case 1a
				RBNode uncle = z.getGrandparent().getRight();
				if (uncle.getColor() == TreeNodeColor.RED) {
					colorChanges += changeColor(z.getParent(),
							TreeNodeColor.BLACK);
					colorChanges += changeColor(uncle, TreeNodeColor.BLACK);
					colorChanges += changeColor(z.getGrandparent(),
							TreeNodeColor.RED);
					z = z.getGrandparent();
				} else {
					if (isRightChild(z)) {
						z = z.getParent();
						leftRotate(z);
					}
					colorChanges += changeColor(z.getParent(),
							TreeNodeColor.BLACK);
					colorChanges += changeColor(z.getGrandparent(),
							TreeNodeColor.RED);
					rightRotate(z.getGrandparent());
				}
			} else {
				RBNode uncle = z.getGrandparent().getLeft(); // y is z uncle
				if (uncle.getColor() == TreeNodeColor.RED) {
					colorChanges += changeColor(z.getParent(),
							TreeNodeColor.BLACK);
					colorChanges += changeColor(uncle, TreeNodeColor.BLACK);
					colorChanges += changeColor(z.getGrandparent(),
							TreeNodeColor.RED);
					z = z.getGrandparent();
				} else {
					if (isLeftChild(z)) {
						z = z.getParent();
						rightRotate(z);
					}
					colorChanges += changeColor(z.getParent(),
							TreeNodeColor.BLACK);
					colorChanges += changeColor(z.getGrandparent(),
							TreeNodeColor.RED);
					leftRotate(z.getGrandparent());
				}
			}
		}

		colorChanges += changeColor(root, TreeNodeColor.BLACK);
		return colorChanges;
	}

	/**
	 * public void delete(int i)
	 * 
	 * deletes the integer i from the binary tree, if it is there; the tree must
	 * remain valid (keep its invariants). the function returns the number of
	 * color flips, or 0 if i was not in the tree
	 * 
	 * O(log(n)), where n=this.size
	 */
	public int delete(int i) {
		int colorChanges = 0;
		RBNode z = nodeSearch(i);
		RBNode y = z;
		TreeNodeColor original_color = y.getColor();
		if (z.getKey() != i) {
			return colorChanges;
		}
		size--;
		RBNode x;
		if (isNil(z.getLeft())) {
			x = isNil(z.getRight()) ? new RBNode(-1, nil, nil, z.getParent(),
					TreeNodeColor.BLACK) : z.getRight();
			transplant(z, z.getRight());
		} else if (isNil(z.getRight())) {
			x = z.getLeft();
			transplant(z, z.getLeft());
		} else {
			y = localMin(z.getRight()); // get the successor
			original_color = y.getColor();
			x = y.getRight();
			if (y.getParent() != z) {/* make sure not to drag children */
				transplant(y, y.getRight());
				y.setRight(z.getRight());
				y.getRight().setParent(y);
			}

			transplant(z, y);
			y.setLeft(z.left);
			y.getLeft().setParent(y);
			colorChanges = changeColor(y, z.getColor());
		}

		if (original_color == TreeNodeColor.BLACK) {
			return colorChanges + deleteFix(x);
		}

		return colorChanges;
	}

	/**
	 * Fixes the color/structure of the RB tree to maintain the black and red
	 * rule
	 * */
	private int deleteFix(RBNode x) {
		int colorChanges = 0;
		while (x != root && x.getColor() == TreeNodeColor.BLACK) {
			if (isLeftChild(x)) {
				RBNode sibling = x.getParent().getRight();
				if (sibling.getColor() == TreeNodeColor.RED) {
					colorChanges += changeColor(sibling, TreeNodeColor.BLACK);
					colorChanges += changeColor(x.getParent(),
							TreeNodeColor.RED);
					leftRotate(x.getParent());
					sibling = x.getParent().getRight();
				}
				if (sibling.getLeft().getColor() == TreeNodeColor.BLACK
						&& sibling.getRight().getColor() == TreeNodeColor.BLACK) {
					colorChanges += changeColor(sibling, TreeNodeColor.RED);
					x = x.getParent();
				} else {
					if (sibling.getRight().getColor() == TreeNodeColor.BLACK) {
						colorChanges += changeColor(sibling.getLeft(),
								TreeNodeColor.BLACK);
						colorChanges += changeColor(sibling, TreeNodeColor.RED);
						rightRotate(sibling);
						sibling = x.getParent().getRight();
					}
					colorChanges += changeColor(sibling, x.getParent()
							.getColor());
					colorChanges += changeColor(x.getParent(),
							TreeNodeColor.BLACK);
					leftRotate(x.getParent());
					x = root;
				}
			} else {
				RBNode sibling = x.getParent().getLeft();
				if (sibling.getColor() == TreeNodeColor.RED) {
					colorChanges += changeColor(sibling, TreeNodeColor.BLACK);
					colorChanges += changeColor(x.getParent(),
							TreeNodeColor.RED);
					rightRotate(x.getParent());
					sibling = x.getParent().getLeft();
				}
				if (sibling.getRight().getColor() == TreeNodeColor.BLACK
						&& sibling.getLeft().getColor() == TreeNodeColor.BLACK) {
					colorChanges += changeColor(sibling, TreeNodeColor.RED);
					x = x.getParent();
				} else {
					if (sibling.getLeft().getColor() == TreeNodeColor.BLACK) {
						colorChanges += changeColor(sibling.getRight(),
								TreeNodeColor.BLACK);
						colorChanges += changeColor(sibling, TreeNodeColor.RED);
						leftRotate(sibling);
						sibling = x.getParent().getLeft();
					}
					colorChanges += changeColor(sibling, x.getParent()
							.getColor());
					colorChanges += changeColor(x.getParent(),
							TreeNodeColor.BLACK);
					rightRotate(x.getParent());
					x = root;
				}
			}
		}
		colorChanges += changeColor(x, TreeNodeColor.BLACK);
		return colorChanges;
	}

	/**
	 * 
	 * returns true if and only if the tree is empty
	 * 
	 * O(1)
	 */
	public boolean empty() {
		return isNil(root);
	}

	/**
	 * public boolean search(int i)
	 * 
	 * returns true if and only if the tree contains i
	 * 
	 * O(log(n)), where n=this.size
	 */
	public boolean search(int i) {
		RBNode n = nodeSearch(i);
		if (n.key == i) {
			return true;
		}
		return false;
	}

	/**
	 * public int min()
	 * 
	 * Returns the smallest key in the tree, or -1 if the tree is empty is
	 * empty, returns -1;
	 * 
	 * O(log(n)), where n=this.size
	 */
	public int min() {
		RBNode min = localMin(root);
		return min.key;
	}

	/**
	 * public int max()
	 * 
	 * Returns the largest key in the tree, or -1 if the tree is empty
	 * 
	 * O(log(n)), where n=this.size
	 */
	public int max() {
		RBNode x = root;
		while (!isNil(x.right)) {
			x = x.right;
		}
		return x.getKey();
	}

	/**
	 * 
	 * returns an int[] array containing the values stored in the tree, in
	 * ascending order.
	 * 
	 * O(n), where n=this.size
	 * 
	 */
	public int[] toIntArray() {
		int[] arr = new int[size];
		toIntArrayIterator = 0;
		toIntArrayUpdate(root, arr);

		return arr;
	}

	/**
	 * 
	 * Returns the number of nodes in the tree.
	 * 
	 * precondition: none postcondition: none
	 * 
	 * O(1)
	 */
	public int size() {
		return size; // to be replaced by student code
	}


	/**
	 * Perform a left rotation
	 * */
	private void leftRotate(RBNode x) {
		RBNode y = x.getRight();

		x.setRight(y.getLeft());
		if (!isNil(x.getRight())) {
			x.getRight().setParent(x);
		}

		y.setParent(x.getParent());
		if (root == x) {
			root = y;
		} else if (isLeftChild(x)) {
			x.getParent().setLeft(y);
		} else {
			x.getParent().setRight(y);
		}

		y.setLeft(x);
		x.setParent(y);
	}

	/**
	 * Perform a right rotation
	 * */
	private void rightRotate(RBNode x) {
		RBNode y = x.getLeft();
		x.setLeft(y.getRight());
		if (!isNil(y.getRight())) {
			y.getRight().setParent(x);
		}
		y.setParent(x.getParent());
		if (x == root) {
			root = y;
		} else if (isRightChild(x)) {
			x.getParent().setRight(y);
		} else {
			x.getParent().setLeft(y);
		}
		y.setRight(x);
		x.setParent(y);
	}

	/**
	 * transplants y in the location of x\
	 */
	private void transplant(RBNode x, RBNode y) {
		if (x == root) {
			root = y;
		} else if (isLeftChild(x)) {
			x.getParent().setLeft(y);
		} else {
			x.getParent().setRight(y);
		}
		if (!isNil(y)) {
			y.setParent(x.getParent());
		}
	}

	/**
	 * return true if x is a right child, false if not.
	 * */
	private boolean isRightChild(RBNode x) {
		return x == x.getParent().getRight();
	}

	/**
	 * return true if x is a left child, false if not.
	 * */
	private boolean isLeftChild(RBNode x) {
		return x == x.getParent().getLeft();
	}

	/**
	 * Updates arr with values from the tree in location which is their position
	 * in the ascending order of the tree
	 * 
	 * This is a recursive call called by toIntArray
	 */
	private void toIntArrayUpdate(RBNode n, int[] arr) {
		if (!isNil(n)) {
			toIntArrayUpdate(n.left, arr);
			arr[toIntArrayIterator] = n.key;
			toIntArrayIterator++;
			toIntArrayUpdate(n.right, arr);
		}
	}

	/**
	 * Returns the node containing the key, and if doesn't exist the node that
	 * would be the parent should we want to create a node in the tree with i as
	 * its key.
	 */
	private RBNode nodeSearch(int i) {
		RBNode n = root;
		RBNode p = n;
		while (!isNil(n)) {
			p = n;
			if (n.key == i) {
				return n;
			} else if (n.key > i) {
				n = n.left;
			} else {
				n = n.right;
			}
		}
		return p;
	}

	private boolean isNil(RBNode x) {
		return x == nil;
	}

	/**
	 * Find the minimum value within a sub tree
	 */
	private RBNode localMin(RBNode x) {
		while (!isNil(x.left)) {
			x = x.left;
		}
		return x;
	}

	/**
	 * Changes the color of a certain node. Returns 1 if the color was actually
	 * changed, 0 if not.
	 */
	private int changeColor(RBNode node, TreeNodeColor color) {
		if (node.getColor() != color) {
			node.setColor(color);
			return 1;
		}
		return 0;
	}

	/**
	 * public class RBNode
	 * 
	 * If you wish to implement classes other than RBTree (for example RBNode),
	 * do it in this file, not in another file
	 * 
	 */
	public class RBNode {
		int key;
		private RBNode left;
		private RBNode right;
		private RBNode parent;
		private TreeNodeColor color;

		public RBNode(int key, RBNode left, RBNode right, RBNode parent,
				TreeNodeColor color) {
			this.key = key;
			this.left = left;
			this.right = right;
			this.parent = parent;
			this.color = color;
		}

		/**
		 * Prints a string representation of the node
		 */
		public String toString() {
			String s = "";
			s = s + "RBNode key: " + key;
			if (left.key == -1) {
				s = s + ", left: NULL";
			} else {
				s = s + ", left: " + left.key;
			}

			if (right.key == -1) {
				s = s + ", right: NULL";
			} else {
				s = s + ", right: " + right.key;
			}
			if (parent.key == -1) {
				s = s + ", parent: NULL";
			} else {
				s = s + ", parent: " + parent.key;
			}

			s = s + ", color: " + color;

			return s;
		}

		/**
		 * 
		 * Returns the grandparent of the node
		 */
		public RBNode getGrandparent() {
			return this.parent.getParent();
		}

		public int getKey() {
			return key;
		}

		public void setKey(int key) {
			this.key = key;
		}

		public RBNode getLeft() {
			return left;
		}

		public void setLeft(RBNode left) {
			this.left = left;
		}

		public RBNode getRight() {
			return right;
		}

		public void setRight(RBNode right) {
			this.right = right;
		}

		public RBNode getParent() {
			return parent;
		}

		public void setParent(RBNode parent) {
			this.parent = parent;
		}

		public TreeNodeColor getColor() {
			return color;
		}

		public void setColor(TreeNodeColor color) {
			this.color = color;
		}

	}

	public enum TreeNodeColor {
		RED, BLACK
	}

	/**
	 * @original author Shai Vardi Modified for semester 2012/2013 a
	 */

}
